The invention relates to the analysis and labeling of individual picture elements (pixels) of a raster-scanned image by utilizing a fixed labeling priority rule, and more particularly to the labeling of pixels positioned adjacent the borders of a raster-scanned image frame.
Automated recognition of objects in raster-scanned images is aided by the technique of connectivity analysis in which the pixels forming a particular object in the scanned image are assigned the same label. An operation for labeling image object pixels was originally set forth by Rosenfeld and Pfaltz in "Sequential Operations and Digital Picture Processing," Journal Of ACM, vol. 14, no. 4, October 1966, pp. 471-494. U.S. Pat. No. 4,183,013 to Agrawala et al. exemplifies a pixel labeling scheme.
With respect to pixel labeling, the pixels forming a given object are said to be connected, and the Rosenfeld reference teaches that the labeling of image pixels involves the two steps of analyzing the connectivity of pixels in the image and labeling of pixels in analyzed image regions.
Pixel connectivity analysis is typically handled by the examination of a neighborhood of pixels surrounding a pixel to be labeled, with the currently-analyzed pixel assigned the value of one of the neighborhood pixels according to a predetermined priority scheme. Using the prioritized neighborhood, the pixels of a raster-scanned image can be analyzed and labeled in the sequence in which they are generated.
Typically, the viewed portion of a raster-scanned image consists of a window that is framed over a larger pixel matrix, so that the viewed portion is surrounded by "undefined pixels" not actually belonging to the viewed image. These undefined pixels are not labeled. However, when the currently-analyzed pixel is adjacent the edge of the viewed portion, the neighborhood employed for its analysis and labeling includes undefined pixels lying outside the framed image window.
When analyzing and labeling pixels on the edge of the viewed portion of a scanned image, previous label selection priority schemes are forced to maintain a set of specialized priority rules, each employed at a respective one of the boundaries of the viewed image. This makes the labeling process difficult, with the challenge being to find an efficient, simplified way of accommodating image boundary conditions so that the undefined pixels do not lead to ambiguous results in component labeling or to complex labeling algorithms.
The ambiguity arises in connectivity labeling schemes from the fact that undefined pixels contain no image information that validly relates them to the pixels forming the currently-viewed portion of an image. Assignment of an arbitrary value to undefined pixels can result in the assignment of an incorrect label to an image boundary pixel if the image boundary pixel's label is selected on the basis of an undefined pixel to which the connectivity scheme determines the image pixel is connected.
Many labeling schemes (such as the Agrawala one referenced previously) employ complex software constructs for pixel analysis and labeling; these are relatively slow-acting and inappropriate for use in high-speed sequential processing such as is implemented in pipelined systems.
Accordingly, the principal object of the present invention is to provide for the unambiguous labeling of image boundary pixels during connected pixel labeling of the image in a sequential manner utilizing a fixed priority rule.
An advantage conferred by achieving this objective is that component labeling according to the present invention can be speedily and efficiently done on a sequential basis, making it particularly suited for high speed pipelined hardware implementation.